#ifndef LEETCODE_CN_CPP_PROBLEMS_988_H
#define LEETCODE_CN_CPP_PROBLEMS_988_H

#include <algorithm>
#include <string>

#include "utils/tree.h"

using namespace std;

namespace problem_988
{

class Solution
{
private:
    string tmp, smallest;

    void helper(TreeNode *root)
    {
        if (root == nullptr)
            return;
        tmp += 'a' + root->val;
        if (root->left == nullptr && root->right == nullptr)
        {
            reverse(tmp.begin(), tmp.end());
            reverse(smallest.begin(), smallest.end());
            if (smallest.empty())
                smallest = tmp;
            else
                smallest = min(smallest, tmp);
            reverse(tmp.begin(), tmp.end());
            reverse(smallest.begin(), smallest.end());
        }
        if (root->left != nullptr)
            helper(root->left);
        if (root->right != nullptr)
            helper(root->right);
        tmp.pop_back();
    }

public:
    string smallestFromLeaf(TreeNode *root)
    {
        tmp.clear();
        smallest.clear();
        helper(root);
        reverse(smallest.begin(), smallest.end());
        return smallest;
    }
};

} // namespace problem_988

#endif //LEETCODE_CN_CPP_PROBLEMS_988_H
